home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / tos / g__~1 / gplibs15.zoo / xbitset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-01  |  18.5 KB  |  975 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <xbitset.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <xobstack.h>
  29. #include <xallocri.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <string.h>
  33. #include <strstrea.h>
  34.  
  35. void BitSet::error(const char* msg) const
  36. {
  37.   (*lib_error_handler)("BitSet", msg);
  38. }
  39.  
  40. //  globals & constants
  41.  
  42. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  43.  
  44. #define ONES               ((unsigned short)(~0L))
  45. #define MAXBitSetRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  46. #define MINBitSetRep_SIZE  16
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD     4
  50. #endif
  51.  
  52. // break things up into .s indices and positions
  53.  
  54.  
  55. // mask out bits from left
  56.  
  57. static inline unsigned short lmask(int p)
  58. {
  59.   return ONES << p;
  60. }
  61.  
  62. // mask out high bits
  63.  
  64. static inline unsigned short rmask(int p)
  65. {
  66.   return ONES >> (BITSETBITS - 1 - p);
  67. }
  68.  
  69.  
  70. inline static BitSetRep* BSnew(int newlen)
  71. {
  72.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  73.     + MALLOC_MIN_OVERHEAD;
  74.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  75.   while (allocsiz < siz) allocsiz <<= 1;
  76.   allocsiz -= MALLOC_MIN_OVERHEAD;
  77.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  78.     (*lib_error_handler)("BitSet", "Requested length out of range");
  79.     
  80.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  81.   bzero(rep, allocsiz);
  82.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  83.   return rep;
  84. }
  85.  
  86. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen, 
  87.                 int newvirt, int newlen)
  88. {
  89.   if (old == &_nilBitSetRep) old = 0; 
  90.   BitSetRep* rep;
  91.   if (old == 0 || newlen >= old->sz)
  92.     rep = BSnew(newlen);
  93.   else
  94.     rep = old;
  95.  
  96.   rep->len = newlen;
  97.   rep->virt = newvirt;
  98.  
  99.   if (srclen != 0 && src != rep->s)
  100.     bcopy(src, rep->s, srclen * sizeof(short));
  101.  
  102.   if (old != rep && old != 0) delete old;
  103.   return rep;
  104. }
  105.  
  106. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  107. {
  108.   BitSetRep* rep;
  109.   if (old == 0 || old == &_nilBitSetRep)
  110.   {
  111.     rep = BSnew(newlen);
  112.     rep->virt = 0;
  113.   }
  114.   else if (newlen >= old->sz)
  115.   {
  116.     rep = BSnew(newlen);
  117.     bcopy(old->s, rep->s, old->len * sizeof(short));
  118.     rep->virt = old->virt;
  119.     delete old;
  120.   }
  121.   else
  122.     rep = old;
  123.  
  124.   rep->len = newlen;
  125.  
  126.   return rep;
  127. }
  128.  
  129. // same, for straight copy
  130.  
  131. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  132. {
  133.   BitSetRep* rep;
  134.   if (old == &_nilBitSetRep) old = 0;
  135.   if (src == 0 || src == &_nilBitSetRep)
  136.   {
  137.     if (old == 0)
  138.       rep = BSnew(0);
  139.     else
  140.       rep = old;
  141.     rep->len = 0;
  142.     rep->virt = 0;
  143.   }
  144.   else if (old == src) 
  145.     return old; 
  146.   else 
  147.   {
  148.     int newlen = src->len;
  149.     if (old == 0 || newlen > old->sz)
  150.     {
  151.       rep = BSnew(newlen);
  152.       if (old != 0) delete old;
  153.     }
  154.     else
  155.       rep = old;
  156.  
  157.     bcopy(src->s, rep->s, newlen * sizeof(short));
  158.     rep->len = newlen;
  159.     rep->virt = src->virt;
  160.   }
  161.   return rep;
  162. }
  163.  
  164.  
  165. // remove unneeded top bits
  166.  
  167. inline static void trim(BitSetRep* rep)
  168. {
  169.   int l = rep->len;
  170.   unsigned short* s = &(rep->s[l - 1]);
  171.  
  172.   if (rep->virt == 0)
  173.     while (l > 0 && *s-- == 0) --l;
  174.   else
  175.     while (l > 0 && *s-- == ONES) --l;
  176.   rep->len = l;
  177. }
  178.  
  179. int operator == (const BitSet& x, const BitSet& y)
  180. {
  181.   return x.rep->len == y.rep->len && x.rep->virt == y.rep->virt &&
  182.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  183.          x.rep->len * sizeof(short)) == 0;
  184. }
  185.  
  186.  
  187. int operator <= (const BitSet& x, const BitSet& y)
  188. {
  189.   if (x.rep->virt > y.rep->virt)
  190.     return 0;
  191.  
  192.   int xl = x.rep->len;
  193.   int yl = y.rep->len; 
  194.  
  195.   unsigned short* xs = x.rep->s;
  196.   unsigned short* ys = y.rep->s;
  197.   unsigned short* topx = &(xs[xl]);
  198.   unsigned short* topy = &(ys[yl]);
  199.  
  200.   while (xs < topx && ys < topy)
  201.   {
  202.     unsigned short a = *xs++;
  203.     unsigned short b = *ys++;
  204.     if ((a | b) != b)
  205.       return 0;
  206.   }
  207.   if (xl == yl)
  208.     return x.rep->virt <= y.rep->virt;
  209.   else if (xl < yl)
  210.     return !x.rep->virt;
  211.   else
  212.     return y.rep->virt;
  213. }
  214.  
  215.  
  216. int operator < (const BitSet& x, const BitSet& y)
  217. {
  218.   if (x.rep->virt > y.rep->virt)
  219.     return 0;
  220.  
  221.   int xl = x.rep->len;
  222.   int yl = y.rep->len;
  223.  
  224.   unsigned short* xs = x.rep->s;
  225.   unsigned short* ys = y.rep->s;
  226.   unsigned short* topx = &(xs[xl]);
  227.   unsigned short* topy = &(ys[yl]);
  228.   int one_diff = 0;
  229.   while (xs < topx && ys < topy)
  230.   {
  231.     unsigned short a = *xs++;
  232.     unsigned short b = *ys++;
  233.     unsigned short c = a | b;
  234.     if (c != b)
  235.       return 0;
  236.     else if (c != a)
  237.       one_diff = 1;
  238.   }
  239.   if (xl == yl)
  240.     return x.rep->virt < y.rep->virt || 
  241.       (one_diff && x.rep->virt == y.rep->virt);
  242.   else if (xl < yl)
  243.     return !x.rep->virt;
  244.   else
  245.     return y.rep->virt;
  246. }
  247.  
  248.  
  249.  
  250. int BitSet::empty() const
  251. {
  252.   if (rep->virt == 1)
  253.     return 0;
  254.  
  255.   unsigned short* bots = rep->s;
  256.   unsigned short* s = &(bots[rep->len - 1]);
  257.   while (s >= bots) if (*s-- != 0) return 0;
  258.   return 1;
  259. }
  260.  
  261.  
  262. int BitSet::count(int b) const
  263. {
  264.   if (b == rep->virt)
  265.     return -1;
  266.   int l = 0;
  267.   unsigned short* s = rep->s;
  268.   unsigned short* tops = &(s[rep->len]);
  269.   if (b == 1)
  270.   {
  271.     while (s < tops)
  272.     {
  273.       unsigned short a = *s++;
  274.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  275.       {
  276.         if (a & 1)
  277.           ++l;
  278.         a >>= 1;
  279.       }
  280.     }
  281.   }
  282.   else
  283.   {
  284.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  285.     while (s < tops)
  286.     {
  287.       unsigned short a = *s++;
  288.       for (int i = 0; i < BITSETBITS; ++i)
  289.       {
  290.         if ((a & maxbit) == 0)
  291.           ++l;
  292.         a <<= 1;
  293.       }
  294.     }
  295.   }
  296.   return l;
  297. }
  298.  
  299. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  300. {
  301.   r = BitSetcopy(r, src);
  302.   r->virt = !src->virt;
  303.   unsigned short* rs = r->s;
  304.   unsigned short* topr = &(rs[r->len]);
  305.   if (r->len == 0)
  306.     *rs = ONES;
  307.   else
  308.   {
  309.     while (rs < topr)
  310.     {
  311.       unsigned short cmp = ~(*rs);
  312.       *rs++ = cmp;
  313.     }
  314.   }
  315.   trim(r);
  316.   return r;
  317. }
  318.  
  319.  
  320. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  321.                     BitSetRep* r, char op)
  322. {
  323.   int xrsame = x == r;
  324.   int yrsame = y == r;
  325.   int xv = x->virt;
  326.   int yv = y->virt;
  327.   int xl = x->len;
  328.   int yl = y->len;
  329.   int rl = (xl >= yl)? xl : yl;
  330.  
  331.   r = BitSetresize(r, rl);
  332.   unsigned short* rs = r->s;
  333.   unsigned short* topr = &(rs[rl]);
  334.  
  335.   int av, bv;
  336.   const unsigned short* as;
  337.   const unsigned short* topa;
  338.   const unsigned short* bs;
  339.   const unsigned short* topb;
  340.   
  341.   if (xl <= yl)
  342.   {
  343.     as = (xrsame)? r->s : x->s;
  344.     av = xv;
  345.     topa = &(as[xl]);
  346.     bs = (yrsame)? r->s : y->s;
  347.     bv = yv;
  348.     topb = &(bs[yl]);
  349.   }
  350.   else
  351.   {
  352.     as = (yrsame)? r->s : y->s;
  353.     av = yv;
  354.     topa = &(as[yl]);
  355.     bs = (xrsame)? r->s : x->s;
  356.     bv = xv;
  357.     topb = &(bs[xl]);
  358.     if (op == '-')              // reverse sense of difference
  359.       op = 'D';
  360.   }
  361.  
  362.   switch (op)
  363.   {
  364.   case '&':
  365.     r->virt = av & bv;
  366.     while (as < topa) *rs++ = *as++ & *bs++;
  367.     if (av)
  368.       while (rs < topr) *rs++ = *bs++;
  369.     else
  370.       while (rs < topr) *rs++ = 0;
  371.     break;
  372.   case '|':
  373.     r->virt = av | bv;
  374.     while (as < topa) *rs++ = *as++ | *bs++;
  375.     if (av)
  376.       while (rs < topr) *rs++ = ONES;
  377.     else
  378.       while (rs < topr) *rs++ = *bs++;
  379.     break;
  380.   case '^':
  381.     r->virt = av ^ bv;
  382.     while (as < topa) *rs++ = *as++ ^ *bs++;
  383.     if (av)
  384.       while (rs < topr) *rs++ = ~(*bs++);
  385.     else
  386.       while (rs < topr) *rs++ = *bs++;
  387.     break;
  388.   case '-':
  389.     r->virt = av & ~(bv);
  390.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  391.     if (av)
  392.       while (rs < topr) *rs++ = ~(*bs++);
  393.     else
  394.       while (rs < topr) *rs++ = 0;
  395.     break;
  396.   case 'D':
  397.     r->virt = ~(av) & (bv);
  398.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  399.     if (av)
  400.       while (rs < topr) *rs++ = 0;
  401.     else
  402.       while (rs < topr) *rs++ = *bs++;
  403.     break;
  404.   }
  405.   trim(r);
  406.   return r;
  407. }
  408.  
  409.  
  410. void BitSet::set(int p)
  411. {
  412.   if (p < 0) error("Illegal bit index");
  413.  
  414.   int index = BitSet_index(p);
  415.   int pos   = BitSet_pos(p);
  416.  
  417.   if (index >= rep->len)
  418.   {
  419.     if (rep->virt)
  420.       return;
  421.     else
  422.       rep = BitSetresize(rep, index+1);
  423.   }
  424.  
  425.   rep->s[index] |= (1 << pos);
  426. }
  427.  
  428. void BitSet::clear()
  429. {
  430.   if (rep->len > 0) bzero(rep->s, rep->sz * sizeof(short));
  431.   rep->len = rep->virt = 0;
  432. }
  433.  
  434. void BitSet::clear(int p)
  435. {
  436.   if (p < 0) error("Illegal bit index");
  437.   int index = BitSet_index(p);
  438.   if (index >= rep->len)
  439.   {
  440.     if (rep->virt == 0)
  441.       return;
  442.     else
  443.       rep = BitSetresize(rep, index+1);
  444.   }
  445.   rep->s[index] &= ~(1 << BitSet_pos(p));
  446. }
  447.  
  448. void BitSet::invert(int p)
  449. {
  450.   if (p < 0) error("Illegal bit index");
  451.   int index = BitSet_index(p);
  452.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  453.   rep->s[index] ^= (1 << BitSet_pos(p));
  454. }
  455.  
  456. void BitSet::set(int from, int to)
  457. {
  458.   if (from < 0 || from > to) error("Illegal bit index");
  459.  
  460.   int index1 = BitSet_index(from);
  461.   int pos1   = BitSet_pos(from);
  462.   
  463.   if (rep->virt && index1 >= rep->len)
  464.     return;
  465.  
  466.   int index2 = BitSet_index(to);
  467.   int pos2   = BitSet_pos(to);
  468.  
  469.   if (index2 >= rep->len)
  470.     rep = BitSetresize(rep, index2+1);
  471.  
  472.   unsigned short* s = &(rep->s[index1]);
  473.   unsigned short m1 = lmask(pos1);
  474.   unsigned short m2 = rmask(pos2);
  475.   if (index2 == index1)
  476.     *s |= m1 & m2;
  477.   else
  478.   {
  479.     *s++ |= m1;
  480.     unsigned short* top = &(rep->s[index2]);
  481.     *top |= m2;
  482.     while (s < top)
  483.       *s++ = ONES;
  484.   }
  485. }
  486.  
  487. void BitSet::clear(int from, int to)
  488. {
  489.   if (from < 0 || from > to) error("Illegal bit index");
  490.  
  491.   int index1 = BitSet_index(from);
  492.   int pos1   = BitSet_pos(from);
  493.   
  494.   if (!rep->virt && index1 >= rep->len)
  495.     return;
  496.  
  497.   int index2 = BitSet_index(to);
  498.   int pos2   = BitSet_pos(to);
  499.  
  500.   if (index2 >= rep->len)
  501.     rep = BitSetresize(rep, index2+1);
  502.  
  503.   unsigned short* s = &(rep->s[index1]);
  504.   unsigned short m1 = lmask(pos1);
  505.   unsigned short m2 = rmask(pos2);
  506.   if (index2 == index1)
  507.     *s &= ~(m1 & m2);
  508.   else
  509.   {
  510.     *s++ &= ~m1;
  511.     unsigned short* top = &(rep->s[index2]);
  512.     *top &= ~m2;
  513.     while (s < top)
  514.       *s++ = 0;
  515.   }
  516. }
  517.  
  518. void BitSet::invert(int from, int to)
  519. {
  520.   if (from < 0 || from > to) error("Illegal bit index");
  521.  
  522.   int index1 = BitSet_index(from);
  523.   int pos1   = BitSet_pos(from);
  524.   int index2 = BitSet_index(to);
  525.   int pos2   = BitSet_pos(to);
  526.  
  527.   if (index2 >= rep->len)
  528.     rep = BitSetresize(rep, index2+1);
  529.  
  530.   unsigned short* s = &(rep->s[index1]);
  531.   unsigned short m1 = lmask(pos1);
  532.   unsigned short m2 = rmask(pos2);
  533.   if (index2 == index1)
  534.     *s ^= m1 & m2;
  535.   else
  536.   {
  537.     *s++ ^= m1;
  538.     unsigned short* top = &(rep->s[index2]);
  539.     *top ^= m2;
  540.     while (s < top)
  541.     {
  542.       unsigned short cmp = ~(*s);
  543.       *s++ = cmp;
  544.     }
  545.   }
  546. }
  547.  
  548.  
  549. int BitSet::test(int from, int to) const
  550. {
  551.   if (from < 0 || from > to) return 0;
  552.  
  553.   int index1 = BitSet_index(from);
  554.   int pos1   = BitSet_pos(from);
  555.   
  556.   if (index1 >= rep->len)
  557.     return rep->virt;
  558.  
  559.   int index2 = BitSet_index(to);
  560.   int pos2   = BitSet_pos(to);
  561.  
  562.   if (index2 >= rep->len)
  563.   {
  564.     if (rep->virt)
  565.       return 1;
  566.     else 
  567.     {
  568.       index2 = rep->len - 1;
  569.       pos2 = BITSETBITS - 1;
  570.     }
  571.   }
  572.  
  573.   unsigned short* s = &(rep->s[index1]);
  574.   unsigned short m1 = lmask(pos1);
  575.   unsigned short m2 = rmask(pos2);
  576.  
  577.   if (index2 == index1)
  578.     return (*s & m1 & m2) != 0;
  579.   else
  580.   {
  581.     if (*s++ & m1)
  582.       return 1;
  583.     unsigned short* top = &(rep->s[index2]);
  584.     if (*top & m2)
  585.       return 1;
  586.     while (s < top)
  587.       if (*s++ != 0) 
  588.         return 1;
  589.     return 0;
  590.   }
  591. }
  592.  
  593. int BitSet::next(int p, int b) const
  594. {
  595.   ++p;
  596.   int index = BitSet_index(p);
  597.   int pos   = BitSet_pos(p);
  598.  
  599.   int l = rep->len;
  600.   
  601.   if (index >= l)
  602.   {
  603.     if (rep->virt == b)
  604.       return p;
  605.     else
  606.       return -1;
  607.   }
  608.   int j = index;
  609.   unsigned short* s = rep->s;
  610.   unsigned short a = s[j] >> pos;
  611.   int i = pos;
  612.  
  613.   if (b == 1)
  614.   {
  615.     for (; i < BITSETBITS && a != 0; ++i)
  616.     {
  617.       if (a & 1)
  618.         return j * BITSETBITS + i;
  619.       a >>= 1;
  620.     }
  621.     for (++j; j < l; ++j)
  622.     {
  623.       a = s[j];
  624.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  625.       {
  626.         if (a & 1)
  627.           return j * BITSETBITS + i;
  628.         a >>= 1;
  629.       }
  630.     }
  631.     if (rep->virt)
  632.       return j * BITSETBITS;
  633.     else
  634.       return -1;
  635.   }
  636.   else
  637.   {
  638.     for (; i < BITSETBITS; ++i)
  639.     {
  640.       if ((a & 1) == 0)
  641.         return j * BITSETBITS + i;
  642.       a >>= 1;
  643.     }
  644.     for (++j; j < l; ++j)
  645.     {
  646.       a = s[j];
  647.       if (a != ONES)
  648.       {
  649.         for (i = 0; i < BITSETBITS; ++i)
  650.         {
  651.           if ((a & 1) == 0)
  652.             return j * BITSETBITS + i;
  653.           a >>= 1;
  654.         }
  655.       }
  656.     }
  657.     if (!rep->virt)
  658.       return j * BITSETBITS;
  659.     else
  660.       return -1;
  661.   }
  662. }
  663.  
  664. int BitSet::previous(int p, int b) const
  665. {
  666.   if (--p < 0)
  667.     return -1;
  668.  
  669.   int index = BitSet_index(p);
  670.   int pos   = BitSet_pos(p);
  671.  
  672.   unsigned short* s = rep->s;
  673.   int l = rep->len;
  674.  
  675.   if (index >= l)
  676.   {
  677.     if (rep->virt == b)
  678.       return p;
  679.     else
  680.     {
  681.       index = l - 1;
  682.       pos = BITSETBITS - 1;
  683.     }
  684.   }
  685.  
  686.   int j = index;
  687.   unsigned short a = s[j];
  688.  
  689.   int i = pos;
  690.   unsigned short maxbit = 1 << pos;
  691.  
  692.   if (b == 1)
  693.   {
  694.     for (; i >= 0 && a != 0; --i)
  695.     {
  696.       if (a & maxbit)
  697.         return j * BITSETBITS + i;
  698.       a <<= 1;
  699.     }
  700.     maxbit = 1 << (BITSETBITS - 1);
  701.     for (--j; j >= 0; --j)
  702.     {
  703.       a = s[j];
  704.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  705.       {
  706.         if (a & maxbit)
  707.           return j * BITSETBITS + i;
  708.         a <<= 1;
  709.       }
  710.     }
  711.     return -1;
  712.   }
  713.   else
  714.   {
  715.     if (a != ONES)
  716.     {
  717.       for (; i >= 0; --i)
  718.       {
  719.         if ((a & maxbit) == 0)
  720.           return j * BITSETBITS + i;
  721.         a <<= 1;
  722.       }
  723.     }
  724.     maxbit = 1 << (BITSETBITS - 1);
  725.     for (--j; j >= 0; --j)
  726.     {
  727.       a = s[j];
  728.       if (a != ONES)
  729.       {
  730.         for (i = BITSETBITS - 1; i >= 0; --i)
  731.         {
  732.           if ((a & maxbit) == 0)
  733.             return j * BITSETBITS + i;
  734.           a <<= 1;
  735.         }
  736.       }
  737.     }
  738.     return -1;
  739.   }
  740. }
  741.  
  742. int BitSet::last(int b) const
  743. {
  744.   if (b == rep->virt)
  745.     return -1;
  746.   else
  747.     return previous((rep->len) * BITSETBITS, b);
  748. }
  749.  
  750.  
  751. extern AllocRing _libgxx_fmtq;
  752.  
  753. const char* BitSettoa(const BitSet& x, char f, char t, char star)
  754. {
  755.   trim(x.rep);
  756.   size_t wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  757.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  758.   ostrstream stream(fmtbase, wrksiz);
  759.   
  760.   x.printon(stream, f, t, star);
  761.   stream << ends;
  762.   return fmtbase;
  763. }
  764.  
  765. #if defined(__GNUG__) && !defined(NO_NRV)
  766.  
  767. BitSet shorttoBitSet(unsigned short w) return r
  768. {
  769.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  770. }
  771.  
  772. BitSet longtoBitSet(unsigned long w) return r;
  773. {
  774.   unsigned short u[2];
  775.   u[0] = w & ((unsigned short)(~(0)));
  776.   u[1] = w >> BITSETBITS;
  777.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  778.   trim(r.rep);
  779. }
  780.  
  781. BitSet atoBitSet(const char* s, char f, char t, char star) return r
  782. {
  783.   int sl = strlen(s);
  784.   if (sl != 0)
  785.   {
  786.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  787.     unsigned short* rs = r.rep->s;
  788.     unsigned short a = 0;
  789.     unsigned short m = 1;
  790.     char lastch = 0;
  791.     unsigned int i = 0;
  792.     unsigned int l = 1;
  793.     for(;;)
  794.     {
  795.       char ch = s[i];
  796.       if (ch == t)
  797.         a |= m;
  798.       else if (ch == star)
  799.       {
  800.         if (r.rep->virt = lastch == t)
  801.           *rs = a | ~(m - 1);
  802.         else
  803.           *rs = a;
  804.         break;
  805.       }
  806.       else if (ch != f)
  807.       {
  808.         *rs = a;
  809.         break;
  810.       }
  811.       lastch = ch;
  812.       if (++i == sl)
  813.       {
  814.         *rs = a;
  815.         break;
  816.       }
  817.       else if (i % BITSETBITS == 0)
  818.       {
  819.         *rs++ = a;
  820.         a = 0;
  821.         m = 1;
  822.         ++l;
  823.       }
  824.       else
  825.         m <<= 1;
  826.     }
  827.     r.rep->len = l;
  828.     trim(r.rep);
  829.   }
  830.   return;
  831. }
  832.  
  833. #else
  834.  
  835. BitSet shorttoBitSet(unsigned short w) 
  836. {
  837.   BitSet r;
  838.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  839.   return r;
  840. }
  841.  
  842. BitSet longtoBitSet(unsigned long w)
  843. {
  844.   BitSet r;
  845.   unsigned short u[2];
  846.   u[0] = w & ((unsigned short)(~(0)));
  847.   u[1] = w >> BITSETBITS;
  848.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  849.   trim(r.rep);
  850.   return r;
  851. }
  852.  
  853. BitSet atoBitSet(const char* s, char f, char t, char star) 
  854. {
  855.   BitSet r;
  856.   int sl = strlen(s);
  857.   if (sl != 0)
  858.   {
  859.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  860.     unsigned short* rs = r.rep->s;
  861.     unsigned short a = 0;
  862.     unsigned short m = 1;
  863.     char lastch = 0;
  864.     unsigned int i = 0;
  865.     unsigned int l = 1;
  866.     for(;;)
  867.     {
  868.       char ch = s[i];
  869.       if (ch == t)
  870.         a |= m;
  871.       else if (ch == star)
  872.       {
  873.         if (r.rep->virt = lastch == t)
  874.           *rs = a | ~(m - 1);
  875.         else
  876.           *rs = a;
  877.         break;
  878.       }
  879.       else if (ch != f)
  880.       {
  881.         *rs = a;
  882.         break;
  883.       }
  884.       lastch = ch;
  885.       if (++i == sl)
  886.       {
  887.         *rs = a;
  888.         break;
  889.       }
  890.       else if (i % BITSETBITS == 0)
  891.       {
  892.         *rs++ = a;
  893.         a = 0;
  894.         m = 1;
  895.         ++l;
  896.       }
  897.       else
  898.         m <<= 1;
  899.     }
  900.     r.rep->len = l;
  901.     trim(r.rep);
  902.   }
  903.   return r;
  904. }
  905.  
  906. #endif
  907.  
  908. ostream& operator << (ostream& s, const BitSet& x)
  909. {
  910.   if (s.opfx())
  911.     x.printon(s);
  912.   return s;
  913. }
  914.  
  915. void BitSet::printon(ostream& s, char f, char t, char star) const
  916. // FIXME:  Does not respect s.width()!
  917. {
  918.   trim(rep);
  919.   register streambuf* sb = s.rdbuf();
  920.   const unsigned short* s = rep->s;
  921.   const unsigned short* top = &(s[rep->len - 1]);
  922.  
  923.   while (s < top)
  924.   {
  925.     unsigned short a = *s++;
  926.     for (int j = 0; j < BITSETBITS; ++j)
  927.     {
  928.       sb->sputc((a & 1)? t : f);
  929.       a >>= 1;
  930.     }
  931.   }
  932.  
  933.   if (!rep->virt)
  934.   {
  935.     unsigned short a = *s;
  936.     if (rep->len != 0)
  937.     {
  938.       for (int j = 0; j < BITSETBITS && a != 0; ++j)
  939.       {
  940.         sb->sputc((a & 1)? t : f);
  941.         a >>= 1;
  942.       }
  943.     }
  944.     sb->sputc(f);
  945.   }
  946.   else
  947.   {
  948.     unsigned short a = *s;
  949.     unsigned short mask = ONES;
  950.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  951.     if (rep->len != 0)
  952.     {
  953.       for (int j = 0; j < BITSETBITS && a != mask; ++j)
  954.       {
  955.         sb->sputc((a & 1)? t : f);
  956.         a = (a >> 1) & himask;
  957.         mask = (mask >> 1) & himask;
  958.       }
  959.     }
  960.     sb->sputc(t);
  961.   }
  962.  
  963.   sb->sputc(star);
  964. }
  965.  
  966. int BitSet::OK() const
  967. {
  968.   int v = rep != 0;             // have a rep
  969.   v &= rep->len <= rep->sz;     // within bounds
  970.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  971.   if (!v) error("invariant failure");
  972.   return v;
  973. }
  974.  
  975.